// @algorithm @lc id=1000020 lang=typescript
// @title re-space-lcci
// @test(["looked","just","like","her","brother"], "jesslookedjustliketimherbrother")  result: 0 ,expect: 7
function respace(dictionary: string[], sentence: string): number {
  // 将词典中的单词放入Trie树中
  const tree: Trie = new Trie();
  for (let word of dictionary) {
    tree.insert(word);
  }
  // 遍历句子中的字符，如果当前位置找到单词，将单词开始位置的索引放入对应的mark数组中
  // mark[i] = [j] 表示从i到j的字符串是单词
  // 因为有的单词会有多个字典匹配，所以mark[i][j]是一个数组
  // 比如:brother，会有borother和her两个字典匹配，所以mark[7] = [0,4]
  const n = sentence.length;
  const mark: number[][] = new Array(n + 1).fill(0).map((_) => []);
  for (let i = 0; i < n; i++) {
    tree.search(sentence, i, mark);
  }
  // 动态规划
  const dp: number[] = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] + 1;
    for (const j of mark[i]) {
      dp[i] = Math.min(dp[i], dp[j]);
    }
  }
  return dp[n];
}

class TrieNode {
  next: TrieNode[] = new Array(26);
  isWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();
  base: number = 'a'.charCodeAt(0);

  insert(word: string) {
    let p = this.root;
    for (const char of word) {
      const idx = char.charCodeAt(0) - this.base;
      if (!p.next[idx]) {
        p.next[idx] = new TrieNode();
      }
      p = p.next[idx];
    }
    p.isWord = true;
  }
  // 记录sentence中搜索到的单词的开始位置的索引
  search(s: string, pos: number, mark: number[][]) {
    let p = this.root;
    for (let i = pos; s[i]; i++) {
      const idx = s.charCodeAt(i) - this.base;
      p = p.next[idx];
      if (p == void 0) break;
      if (p.isWord) {
        mark[i + 1].push(pos);
      }
    }
  }
}
